package ycj.learn.dsa.leetcode;

/**
 *
 * 分治，然后两两合并。时间也太tm久了嘛
 *
 */
public class MergeKLists {
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    private ListNode merge(ListNode[] lists, int l, int r) {
        if (l > r) return null;
        if (l == r) {
            return lists[l];
        }

        if (r == l + 1) {
            return mergeTwo(lists[l], lists[r]);
        }
        int k = r - l / 2;

        return mergeTwo(merge(lists, l, k - 1), merge(lists, k, r));
    }

    private ListNode mergeTwo(ListNode n1, ListNode n2) {
        ListNode guard = new ListNode(0);
        ListNode hot = guard;

        while (n1 != null || n2 != null) {
            if (n1 == null || (n2 != null && n1.val >= n2.val)) {
                hot.next = n2;
                hot = hot.next;
                n2 = n2.next;
                continue;
            }

            hot.next = n1;
            hot = hot.next;
            n1 = n1.next;
        }

        return guard.next;
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}

